Multi-evolutionary Features Based Link Prediction Algorithm for Social Network
HE Yulin1,2, LAI Junlong2, CUI Laizhong1,2, HUANG Zhexue1,2, YIN Jianfei2
1. Guangdong Laboratory of Artificial Intelligence and Digital Economy(SZ), Shenzhen 518107; 2. Big Data Institute, Shenzhen University, Shenzhen 518060
摘要 社交网络链路预测旨在根据已知的网络信息预测未来的链接关系,在推荐系统和合著网络中具有重要作用.然而,现有链路预测算法往往忽视社交网络的多元演化特点,训练时间复杂度较高,限制其执行效率.针对上述问题,文中提出基于多演化特征的社交网络链路预测算法(Multi-evolutionary Features Based Link Prediction Algorithm for Social Network, MEF-LP).首先,设计一种简单高效的时间极限学习机模型,利用门控网络和极限学习机自编码器传递与聚合社交网络快照序列的时间信息.然后,构建多个深度极限学习机,对时间特征进行多角度映射,挖掘社交网络不同的演化特征,并最终融合成综合演化特征.最后,使用基于极限学习机的分类器完成链路预测.在6个真实社交网络上的实验表明,MEF-LP能合理学习社交网络的多演化特征,并获得较优的预测性能.
Abstract：Social network link prediction aims to predict future link relationships based on known network information, in which there are important applications for recommender systems and co-authorship networks. However, existing link prediction algorithms often ignore multi-evolutionary features of social networks and have high training time complexity, limiting their execution efficiency and application performance. To address these problems, a multi-evolutionary features based link prediction algorithm for social network(MEF-LP) is proposed. Firstly, a simple and efficient time extreme learning machine model is designed to transfer and aggregate the temporal information of social network snapshot sequences, using gated networks and extreme learning machine self-encoders. Secondly, multiple multilayer extreme learning machines are constructed to map temporal features from multiple perspectives, mining different evolutionary features of social networks and ultimately integrating them into comprehensive evolutionary features. Finally, the extreme learning machine-based classifiers are utilized to complete the link prediction. Experiments on six real social networks show that MEF-LP can reasonably learn the multi-evolution features of social networks and achieve better prediction performance.
何玉林, 赖俊龙, 崔来中, 黄哲学, 尹剑飞. 基于多演化特征的社交网络链路预测算法[J]. 模式识别与人工智能, 2024, 37(7): 597-612.
HE Yulin, LAI Junlong, CUI Laizhong, HUANG Zhexue, YIN Jianfei. Multi-evolutionary Features Based Link Prediction Algorithm for Social Network. Pattern Recognition and Artificial Intelligence, 2024, 37(7): 597-612.
[1] NASIRI E, BERAHMAND K, SAMEI Z, et al. Impact of Centrality Measures on the Common Neighbors in Link Prediction for Multiplex Networks. Big Data, 2022, 10(2): 138-150. [2] VITAL A, AMANCIO D R. A Comparative Analysis of Local Similarity Metrics and Machine Learning Approaches: Application to Link Prediction in Author Citation Networks. Scientometrics, 2022, 127(10): 6011-6028. [3] ORZECHOWSKI K P, MROWINSKI M J, FRONCZAK A, et al. Asymmetry of Social Interactions and Its Role in Link Predictability: The Case of Coauthorship Networks. Journal of Informetrics, 2023, 17(2). DOI: 10.1016/j.joi.2023.101405. [4] MA Z M, NANDY S. Community Detection with Contextual Multilayer Networks. IEEE Transactions on Information Theory, 2023, 69(5): 3203-3239. [5] ADAMIC L A, ADAR E. Friends and Neighbors on the Web. Social Networks, 2003, 25(3): 211-230. [6] KATZ L. A New Status Index Derived from Sociometric Analysis. Psychometrika, 1953, 18(1):39-43. [7] NEWMAN M E J. Clustering and Preferential Attachment in Growing Networks. Physical Review E, 2001, 64(2). DOI: 10.1103/Phys-RevE.64.025102. [8] ZHOU T, LÜ L Y, ZHANG Y C. Predicting Missing Links via Local Information. The European Physical Journal B, 2009, 71(4): 623-630. [9] JEH G, WIDOM J. SimRank: A Measure of Structural-Context Simi-larity // Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2002: 538-543. [10] LÜ L Y, JIN C H, ZHOU T. Similarity Index Based on Local Paths for Link Prediction of Complex Networks. Physical Review E, 2009, 80(4). DOI: 10.1103/PhysRevE.80.046122. [11] KUMARI A, BEHERA R K, SAHOO K S, et al. Supervised Link Prediction Using Structured-Based Feature Extraction in Social Network. Concurrency and Computation: Practice and Experience, 2022, 34(13). DOI: 10.1002/cpe.5839. [12] KUMAR S, MALLIK A, PANDA B S. Link Prediction in Complex Networks Using Node Centrality and Light Gradient Boosting Machine. World Wide Web, 2022, 25(6): 2487-2513. [13] LIU X Y, LI X. A Social Network Link Prediction Method Based on Stacked Generalization. The Computer Journal, 2022, 65(10): 2693-2708. [14] CHAUBEY V P, SHARMA A, SHARMA T, et al. Link Prediction for Social Network Analysis Using Random Forest and XG-Boost Algorithm // Proc of the 2nd International Conference on Informatics. Washington, USA: IEEE, 2023. DOI: 10.1109/ICI60088.2023.10421655. [15] AHMED N M, CHEN L, WANG Y L, et al. DeepEye: Link Prediction in Dynamic Networks Based on Non-negative Matrix Factorization. Big Data Mining and Analytics, 2018, 1(1): 19-33. [16] MA X K, SUN P G, WANG Y. Graph Regularized Nonnegative Matrix Factorization for Temporal Link Prediction in Dynamic Networks. Physica A: Statistical Mechanics and Its Applications, 2018, 496: 121-136. [17] MAHMOODI R, SEYEDI S A, TAB F A, et al. Link Prediction by Adversarial Nonnegative Matrix Factorization. Knowledge-Based Systems, 2023, 280. DOI: 10.1016/j.knosys.2023.110998. [18] NASIRI E, BERAHMAND K, LI Y F. Robust Graph Regularization Nonnegative Matrix Factorization for Link Prediction in Attributed Networks. Multimedia Tools and Applications, 2023, 82(3): 3745-3768. [19] CHEN G F, WANG H B, FANG Y L, et al. Link Prediction by Deep Non-negative Matrix Factorization. Expert Systems with Applications, 2022, 188. DOI: 10.1016/j.eswa.2021.115991. [20] MA X K, TAN S Y, XIE X H,et al. Joint Multi-label Learning and Feature Extraction for Temporal Link Prediction. Pattern Re-cognition, 2022, 121. DOI: 10.1016/j.patcog.2021.108216. [21] YU W C, AGGARWAL C C, WANG W. Temporally Factorized Network Modeling for Evolutionary Network Analysis // Proc of the 10th ACM International Conference on Web Search and Data Mi-ning. New York, USA: ACM, 2017: 455-464. [22] YU W C, CHENG W, AGGARWAL C C, et al. Link Prediction with Spatial and Temporal Consistency in Dynamic Networks // Proc of the 26th International Joint Conference on Artificial Intelligence. San Francisco, USA: IJCAI, 2017: 3343-3349. [23] CHEN J Y, ZHANG J, XU X H, et al. E-LSTM-D: A Deep Lear-ning Framework for Dynamic Network Link Prediction. IEEE Transactions on Systems, Man, and Cybernetics(Systems), 2021, 51(6): 3699-3712. [24] JIAO P F, GUO X, JING X, et al. Temporal Network Embedding for Link Prediction via VAE Joint Attention Mechanism. IEEE Tran-sactions on Neural Networks and Learning Systems, 2021, 33(12): 7400-7413. [25] CHEN J Y, WANG X K, XU X H. GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Network Link Prediction. Applied Intelligence, 2022, 52: 7513-7528. [26] TAN S Y, YOU J Y, LI D Y. Temporality- and Frequency-Aware Graph Contrastive Learning for Temporal Network // Proc of the 31st ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2022: 1878-1888. [27] MEI P, ZHAO Y H. Dynamic Network Link Prediction with Node Representation Learning from Graph Convolutional Networks. Scientific Reports, 2024, 14(1). DOI: 10.1038/s41598-023-50977-6. [28] QIN M, ZHANG C R, BAI B,et al. High-Quality Temporal Link Prediction for Weighted Dynamic Graphs via Inductive Embedding Aggregation. IEEE Transactions on Knowledge and Data Enginee-ring, 2023, 35(9): 9378-9393. [29] YIN Y T, WU Y J, YANG X B, et al. Super Resolution Graph with Conditional Normalizing Flows for Temporal Link Prediction. IEEE Transactions on Knowledge and Data Engineering, 2024, 36(3): 1311-1327. [30] ZHOU L K, YANG Y, REN X, et al. Dynamic Network Embe-dding by Modeling Triadic Closure Process. Proceedings of the AAAI Conference on Artificial Intelligence, 2018, 32(1): 571-578. [31] SANKAR A, WU Y H, GOU L, et al. DySAT: Deep Neural Re-presentation Learning on Dynamic Graphs via Self-Attention Networks // Proc of the 13th International Conference on Web Search and Data Mining. New York, USA: ACM, 2020: 519-527. [32] HUANG G B, ZHU Q Y, SIEW C K. Extreme Learning Machine: Theory and Applications. Neurocomputing, 2006, 70(1/2/3): 489-501. [33] HUANG G B, ZHOU H M, DING X J, et al. Extreme Learning Machine for Regression and Multiclass Classification. IEEE Transactions on Systems, Man, and Cybernetics(Cybernetics), 2012, 42(2): 513-529. [34] RAO C R, MITRA S K. Generalized Inverse of a Matrix and Its Applications // Proc of the 6th Berkeley Symposium on Mathematical Statistics and Probability. Oakland, USA: University of California Press, 1972: 601-620. [35] HUANG G, HUANG G B, SONG S J, et al. Trends in Extreme Learning Machines: A Review. Neural Networks, 2015, 61: 32-48. [36] HUANG G B, BAI Z, LEKAMALAGE L, et al. Local Receptive Fields Based Extreme Learning Machine. IEEE Computational Intelligence Magazine, 2015, 10(2): 18-29. [37] LEI K, QIN M, BAI B, et al. GCN-GAN: A Non-linear Temporal Link Prediction Model for Weighted Dynamic Networks // Proc of the IEEE Conference on Computer Communications. Washington, USA: IEEE, 2019: 388-396. [38] FIRE M, TENENBOIM L, LESSER O, et al. Link Prediction in Social Networks Using Computationally Efficient Topological Features // Proc of the IEEE 3rd International Conference on Privacy, Security, Risk and Trust and IEEE 3rd International Conference on Social Computing. Washington, USA: IEEE, 2011: 73-80. [39] HUANG Z, LI X, CHEN H. Link Prediction Approach to Collaborative Filtering // Proc of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries. New York, USA: ACM, 2005: 141-142. [40] QI Y, LUO J W. Prediction of Essential Proteins Based on Local Interaction Density. IEEE/ACM Transactions on Computational Bio-logy and Bioinformatics, 2016, 13(6): 1170-1182. [41] RIQUELME F, GONZALEZ-CANTERGIANI P, MOLINERO X, et al. Centrality Measure in Social Networks Based on Linear Thre-shold Model. Knowledge-Based Systems, 2018, 140: 92-102. [42] SCARDONI G, PETTERLINI M, LAUDANNA C. Analyzing Biological Network Parameters with CentiScaPe. Bioinformatics, 2009, 25(21): 2857-2859. [43] KLEINBERG J M. Authoritative Sources in a Hyperlinked Environ-ment. Journal of the ACM, 1999, 46(5): 604-632. [44] BRIN S, PAGE L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7): 107-117.
2024, Vol. 37 
